public class Leetcode1124 {

    public static void main(String[] args) {
        System.out.println(longestWPI(new int[]{9, 9, 6, 0, 6, 6, 9}) == 3);
        System.out.println(longestWPI(new int[]{6, 6, 6}) == 0);
        System.out.println(longestWPI(new int[]{8, 8, 8}) == 0);
        System.out.println(longestWPI(new int[]{6, 9, 9}) == 3);
        System.out.println(longestWPI(new int[]{9, 6, 9}) == 3);
        System.out.println(longestWPI(new int[]{6, 6, 9}) == 1);
        System.out.println(longestWPI(new int[]{9, 9, 6}) == 3);
        System.out.println(longestWPI(new int[]{6, 9, 6}) == 1);
        System.out.println(longestWPI(new int[]{9, 6, 6, 9, 9}) == 5);
        System.out.println(longestWPI(new int[]{8, 12, 7, 6, 10, 10, 9, 11, 12, 6}) == 10);
        System.out.println(longestWPI(new int[]{8, 10, 6, 16, 5}) == 3);
    }

    public static int longestWPI(int[] hours) {
        int[] prefixAndOne = new int[hours.length];
        int[] prefixAndZero = new int[hours.length];

        int oneNumber = 0;
        int zeroNumber = 0;
        for (int i = hours.length - 1; i >= 0; i--) {
            prefixAndOne[i] = oneNumber;
            prefixAndZero[i] = zeroNumber;

            if (hours[i] > 8) {
                oneNumber++;
            } else {
                zeroNumber++;
            }
        }

        int res = 0;
        int tiringTime = 0;
        int notTiringTime = 0;
        int currentDay = 0;
        for (int i = 0; i < hours.length; i++) {
            if (hours[i] > 8) {
                ++tiringTime;
            } else {
                ++notTiringTime;
            }

            ++currentDay;
            if (tiringTime > notTiringTime) {
                res = Math.max(currentDay, res);
            } else {
                if (prefixAndOne[i] + tiringTime <= prefixAndZero[i] + notTiringTime) {
                    tiringTime = 0;
                    notTiringTime = 0;
                    currentDay = 0;
                }
            }
        }

        return res;
    }

}
